#include <queue>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution
{
public:
    static int minMutation(const string& startGene, const string& endGene, vector<string>& bank)
    {
        pmr::unordered_set<string> visit;
        unordered_set<string> hash(bank.begin(), bank.end());
        queue<string> q;
        q.emplace(startGene);
        visit.insert(startGene);
        int ret = 0;
        string change = "ACGT";

        while(!q.empty())
        {
            ret++;
            int sz = q.size();
            while(sz--)
            {
                string t = q.front();
                q.pop();
                for(int s=0; s<8; s++)//每个字符
                {
                    string tmp = t;
                    for(int k=0; k<4; k++)//每个字符的每种变化
                    {
                        tmp[s] = change[k];
                        if(hash.count(tmp) && !visit.count(tmp))//变了之后能在bank中找到且没有变到过，即为有效变换
                        {
                            if(tmp == endGene)
                                return ret;
                            q.emplace(tmp);
                            visit.insert(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};